package esercitazione5.graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Classe che implementa algoritmo MST per ottenere il grafo di copertura minimo.
 *
 * @param <V>
 * @param <E>
 */
public class MST<V, E extends Comparable<E>> {

	// Grafo su cui si effettuano le operazioni di visita.
	private GraphInterface<V,E> g;

	/**
	 * Costruttore che inizializza il grafo
	 */
	public MST(GraphInterface<V, E> g){
		this.g = g;
	}

	/**
	 * Metodo per ottenere la lista di archi ordinati per peso
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private List<Edge<V>> orderEdges(){
		// Struttura inizialmente vuota che poi sarà riempita da archi ordinati per peso
		List<Edge<V>> edges = new ArrayList<Edge<V>>();

		// Per ogni arco del grafo...
		for(Edge<V> edge : g.edges()){
			// ...preso il suo peso...
			String prop = "weight";
			E value = (E) edge.getProperty(prop);
			// ...se la struttura di archi ordinati è vuota, inserisco l'arco corrente...
			if(edges.size() == 0)
				edges.add(edge);
			// ...altrimenti...
			else{
				// ...per ogni arco già ordinato...
				for(int i = 0; i < edges.size(); i++)
					// ...se il peso dell'arco corrente è minore...
					if(value.compareTo((E) edges.get(i).getProperty(prop)) <= 0){
						// ...aggiungo l'arco corrente in quella posizione.
						edges.add(i, edge);
						break;
					}

				// Se il peso dell'arco corrente è maggiore di quello di tutti gli archi già ordinati lo aggiungo in coda.
				if(value.compareTo((E) edges.get(edges.size()-1).getProperty(prop)) > 0)
					edges.add(edge);
			}
		}
		// Ritorno la lista di archi ordinati per peso.
		return edges;
	}

	/**
	 * Algoritmo di kruskal per individuare la soluzione minima di copertura di tutti i vertici del grafo.
	 * L'algoritmo calcola la soluzione finale (che non è unica) in maniera incrementale.
	 * @return
	 */
	public List<Edge<V>> kruskal(){
		// Ordino gli edges del grafo
		List<Edge<V>> edges = orderEdges();
		// Inizializzo una collezione che conterrà i gruppi di archi connessi (risultati parziali dell'algoritmo)
		Map<Integer, ArrayList<Vertex<V>>> group = new HashMap<Integer, ArrayList<Vertex<V>>>();
		// Inizializzo la struttura che conterrà gli archi di copertura finali
		List<Edge<V>> minEdges = new ArrayList<Edge<V>>();

		// Inizializzo le strutture
		int count = 1;
		// Per ogni vertice inserisco, creo una lista vuota di vertici, e la inserisco nella struttura 'group'
		// dove ogni Group è caratterizzato da un ID univoco.
		for(Vertex<V> v : g.vertices()){
			ArrayList<Vertex<V>> list = new ArrayList<Vertex<V>>();
			list.add(v);
			group.put(count, list);
			v.addProperty("idGroup", count++);
		}

		// Ciclo su tutti gli archi
		for(Edge<V> e : edges){
			// Prendo i vertici sorgente e destinazione
			Vertex<V> s = e.getSource();
			Vertex<V> d = e.getDestination();

			// Se l'id dei gruppi dei due vertici è diverso
			if(s.getProperty("idGroup") != d.getProperty("idGroup")){
				// Se il gruppo sorgente ha più elementi di quelli destinazione
				if(group.get(s.getProperty("idGroup")).size() >= group.get(d.getProperty("idGroup")).size()){
					int idD = (Integer) d.getProperty("idGroup");
					// Tutti gli elementi legati al gruppo di destinazione vengono copiati nell'altro gruppo
					// e il loro id viene aggiornato
					for(Vertex<V> v: group.get(d.getProperty("idGroup"))){
						v.addProperty("idGroup", s.getProperty("idGroup"));
						group.get(s.getProperty("idGroup")).add(v);
					}
				}
				// Se il gruppo destinazione ha più elementi di quelli sorgente
				else{
					int idS = (Integer) d.getProperty("idGroup");
					// Tutti gli elementi legati al gruppo di sorgente vengono copiati nell'altro gruppo
					// e il loro id viene aggiornato
					for(Vertex<V> v: group.get(s.getProperty("idGroup"))){
						v.addProperty("idGroup", d.getProperty("idGroup"));
						group.get(d.getProperty("idGroup")).add(v);
					}
				}
				// Aggiungo agli archi minimi l'arco corrente.
				minEdges.add(e);
			}
		}
		// Restituisco l'elenco finale di archi, ordinati in modo da avere copertura minima del grafo.
		return minEdges;
	}

	public static void main(String[] args) {

		GraphInterface<Integer, Integer> g = new Graph<Integer, Integer>();
		Vertex<Integer> uno = g.insertVertex(1);
		Vertex<Integer> due = g.insertVertex(2);
		Vertex<Integer> tre = g.insertVertex(3);
		Vertex<Integer> quattro = g.insertVertex(4);
		Vertex<Integer> cinque = g.insertVertex(5);
		Vertex<Integer> sei = g.insertVertex(6);
		Vertex<Integer> sette = g.insertVertex(7);
		Vertex<Integer> otto = g.insertVertex(8);
		Vertex<Integer> nove = g.insertVertex(9);
		Vertex<Integer> dieci = g.insertVertex(10);
		Vertex<Integer> undici = g.insertVertex(11);

		g.insertEdge(due, tre, 3);
		g.insertEdge(due, cinque, 10);
		g.insertEdge(quattro, cinque, 4);
		g.insertEdge(quattro, dieci, 1);
		g.insertEdge(cinque, sette, 4);
		g.insertEdge(sette, uno, 3);
		g.insertEdge(sette, nove, 6);
		g.insertEdge(uno, undici, 13);
		g.insertEdge(sei, otto, 2);
		g.insertEdge(dieci, sette, 11);
		g.insertEdge(sei, cinque, 4);
		g.insertEdge(cinque, cinque,1);
		g.insertEdge(sei, sette, 34);
		g.insertEdge(dieci, quattro, 1);

		System.out.println("edges ordinati:");
		MST<Integer,Integer> mst = new MST<>(g);
		for(Edge<Integer> e : mst.orderEdges()){
			System.out.println(e.getSource().getValue()+" ---> "+e.getDestination().getValue()+"	peso:	"+e.getProperty("weight"));
		}
		System.out.println();
		
		System.out.println("kruskal:");
		for(Edge<Integer> e : mst.kruskal()){
			System.out.println(e.getSource().getValue()+" ---> "+e.getDestination().getValue()+"	id source:	"+e.getSource().getProperty("idGroup")+"	id dest:	"+e.getDestination().getProperty("idGroup"));
		}

	}
}
